package 算法基础模板.chapter_02.并查集;

/**
 * 合并两个集合
 * 询问两个元素是否在同一个集合当中
 * <p>
 * 基本原理: 每个集合用一颗树表示,树根的编号就是整个集合的编号,每个节点存储它的父节点, p[x] 表示x的父节点
 * <p>
 * 问题1 : 如何判断树根 if(p[x] == x)
 * 问题2 : 如何求x的集合编号  while ( p[x] != x ) x = p[x];
 * 问题3 : 如何合并两个集合: px 是x的集合编号, py是y的集合编号  p[x] = y;
 *
 * @author Summerday
 */
public class UnionFind {

    int[] p;
    int[] size;

    UnionFind(int n) {
        p = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
            size[i] = 1;
        }
    }

    void union(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px == py) return;
/*        if (size[px] < size[py]) {
            p[px] = py;
            size[py] += size[px];
        } else {
            p[py] = px;
            size[px] += size[py];
        }*/

        p[px] = py;
        size[py] += size[px];

    }

    int getPxCnt(int x) {
        return size[find(x)];
    }


    int find(int x) {
        // 如果父节点不是祖宗节点, 就让父节点 为 祖宗节点
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }

}
